package god.dao01;

/**
 * @author wang hao
 * @date 2023-02-18 12:25
 *
 *      int类型的数  提取出最右侧的 1
 *
 *      一个数组中两个数 出现了 奇数次, 其他的数都出现了偶数次  找出这两个奇数    getTwo()
 *
 *      一个数组中 有一种数出现了 K次，其他数都出现了M次     onlyKTimes
 *       其中    M > 1,  K < M
 *       找见这个k
 *       要求 空间复杂度为 o(1)
 *
 *
 */
public class Demo05 {

    public static void main(String[] args) {
        System.out.println(~20 + 1); // -20
        int[] arr = new int[]{1, 2, 3, 3, 4, 4, 6, 6};
        getTwo(arr);


        arr = new int[]{7, 7, 3, 3, 3, 4, 4, 4};
        int i = onlyKTimes(arr, 2, 3);
        System.out.println(i);
    }

    public static void getTwo(int[] arr){
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }

        // 此时的 eor 是 a ^ b 的结果       a 和 b  是两种数  所以 a ^ b 是一定不等于0的
        int rightOne = eor & (~eor + 1);  // 提取出 eor 最右边的1
        int onlyOne = 0; // eor'
        for (int i = 0; i < arr.length; i++) {
            // arr[1]   111100011110000
            //rightOne  000000000010000     只跟左侧为1的数进行 异或操作
            if ((arr[i] & rightOne) != 0){
                onlyOne ^= arr[i];
            }
        }

        // 下面这两个数 就是 出现奇数次的 数
        System.out.println(onlyOne);
        System.out.println(onlyOne ^ eor);
    }


    // 请保证arr中, 只有一种数出现了K次，其他数都出现了M次
    public static int onlyKTimes(int[] arr, int k, int m){
        int[] t = new int[32];
        // t[0] 位置 代表  0位置的1出现了几个
        for (int num : arr) {
             for (int i = 0; i < 32; i++) {
                 // t[i] += (num >> i) & 1   优化版本
                 if (((num >> i) & 1) != 0){  // 判断 num 在第 i位置 是否 为 0  如果不等于0 说明 num >> 1 的最后一个是 1
                     t[i]++;
                 }
             }
        }

        int ans = 0;
        for (int i = 0; i < t.length; i++) {
            if (t[i] % m != 0){
                // ans   00000000
                // i     00000001
                ans |= (1 << i);
            }
        }
        return ans;
    }
}
